The present invention generally relates to an electronic circuit design system implemented by using an electronic computer. More specifically, the invention is concerned with a wire routing apparatus for automatically designing a wiring pattern for printed boards or substrates and very large scale integrated circuits or VLSIs.
As a typical one of procedures for searching wiring paths or routes in VLSIs, there has already been developed and widely used what is called a maze routing algorithm as well as modified or improved methods thereof. According to the maze routing algorithm, a wire routing area in which wires are to be embedded is divided or partitioned into a plurality of subareas referred to as meshes or mesh points. One of two mesh points which are to be wired together is selected as a starting point, whereon a processing for marking neighbor mesh points through which the wiring path can extend is iterated from one to another mesh point, beginning with the starting point, for thereby detecting a shortest wiring path leading to a sink or target point. Further, as an approach to improve the quality of the routing technique, a method is proposed in which cost involved in the wiring is taken into consideration during the wiring path finding process. In this conjunction, the cost is determined on the basis of information concerning the situations or states of the routing area and/or information concerning the direction in which the wiring path search progresses. The wire routing process is controlled by taking into account the cost. Searching cost is defined as weighting information for determining the priority order of several seachable routes.
An example of such a wire routing procedure will be explained by reference to FIGS. 3A and 3B of the accompanying drawings. FIG. 3A diagrammatically illustrates an example of the maze routing algorithm in which the cost is put aside from consideration. In both of FIGS. 3A and 3B, a symbol S denotes a starting point for the route searching and T denotes a sink or target point thereof. In the figures, hatched areas indicate blockage or obstacle subareas or meshes which inhibit the wiring therethrough. Further, meshes shown in these figures correspond to the mesh points in an actual routing area, wherein numerals inserted in the meshes represent the total of the wiring costs. In the case of the maze routing algorithm illustrated in FIG. 3A, the total wiring cost is uniformly incremented by "1" as the wiring path trace proceeds to any one of the neighbor mesh points regardless of the routing or tracing directions because no consideration is paid to the cost. Consequently, the searching forefront referred to as the wavefront will spread or propagate concentrically around the starting point S. When the total wiring cost amounts to "9", this means that the route or wiring path has been traced up to the sink or target point T.
On the other hand, FIG. 3B shows an example of the maze routing algorithm in which the cost is taken into consideration during the searching process. According to the method illustrated in FIG. 3B, the total of the cost is incremented by "+2" every time the route being traced turns, while it is incremented by "+1" so long as the wiring path can be routed straightforwardly without changing the direction. In case one and the same mesh point is allocated with a plurality of different costs, the tracing direction involving the least cost is selected with preference over the others. By searching the wiring path under these conditions, there can be found the wiring path having the least number of turns (i.e. changes in the tracing direction).
The processing described above is implemented by software running on a general-purpose computer and generally takes an intolerably long time, because substantially all the mesh points of the routing area have to be checked.
According to a wire routing method and apparatus disclosed in S. J. Hong, R. Nair "Wire-Routing Machines--New Tools for VLSI Physical Design", PROCEEDING OF THE IEEE, Vol. 71, No. 1, pp. 57-65, January 1983, U.S. Pat. Nos. 4,484,292 and 4,593,351, the wire routing is carried out by a parallel computer system which includes a plurality of parallel processors interconnected in a mesh array (mesh-connected multiprocessor complex). These known routing schemes are founded on the fact that the wavefront processing mentioned above is susceptible to parallel execution, and thus processings of the mesh points covered by the wavefront are allocated to a plurality of processors capable of operating in parallel. More specifically, element processors are allocated to the mesh points within the area of concern in one-to-one correspondence, wherein upon propagation of search information from the element processor allocated to a given one of the neighbor mesh points, the search information is also transmitted to the other processors allocated to the remaining neighbor mesh points, respectively. Further, Japanese Patent Publication JP-B-58-42621 discloses a wire routing apparatus which comprises a plurality of mesh-connected processing units each constituted by a memory element which can be controlled externally. In a parallel wire routing scheme taught in JP-A-62-115574, a wiring area is partitioned into a plurality of subareas, wherein wirings in these subareas are executed by a number of cell computers assigned to these subareas, respectively.
As previously described, the processing for searching the wiring paths requires such an enormous amount of time that wiring for an LSI of the next generation will take a time on the order of 100 hours even if a large scale computer of the highest speed available at present is used. Such being the circumstances, the rewriting resulting from changes in the design as well as manufacturing of various LSIs on a small production basis exerts serious influence to assuarance of good productivity. Accordingly, there exists a great demand for a faster wire routing technique from the economical standpoint as well.
The problems mentioned above are believed to be ascribable to the fact that the wire routing processing is executed by software running on a general-purpose computer system. More specifically, with the software, the wire routing functions mentioned above are realized through sequential and iterative processings by combining basic instructions such as assignment processing, arithmetic processing, execution control processing and others. On the other hand, the wiring path search processing can be executed simultaneously for a plurality of locations within a routing area through a so-called parallel processing. However, in the parallel computer complex in which element processors are simply connected in a mesh-structure as in the case of the prior art wire routing systems mentioned above, the number of the processors actually put into parallel operations during the search processing is limited even when a great number of processors are provided. This means that the improvement with respect to the processing speed unfortunately remains low notwithstanding increases in the amount of hardware employed. More concretely, in the case of the prior art technique based on the maze routing algorithm, data susceptible to the parallel processing is only the one-dimensional data constituting the wavefront. Consequently, even when the data processing is dispersed or distributed to a plurality of processors arrayed two-dimensionally or three-dimensionally, a majority of processors can not operate simultaneously. Furthermore, since the processing speed of the prior art routing system can not be improved more than by a factor corresponding to a value several times as large as the number of the mesh points belonging to the wavefront at the most and because the individual processors execute simple processing by using software, the low-speediness of the processing can not be improved to any appreciable extent. Besides, in the parallel processing system in which the routing area is divided into plural subareas, coordinated operations of the cell computers are necessary for execution of the wire routing across and through a plurality of subareas, which will unavoidably be accompanied with lowering in the processing speed.